(1) Field of the Invention
The present invention relates to a system and a method for tracking vehicles using random search algorithm methodolgies.
(2) Description of the Prior Art
Contact tracking encompasses processing data from various sensors to provide an estimate of a contact's position and velocity, or state. Under favorable noise, geometric and environmental conditions, or highly observable conditions, reliable unique estimates of the target state can be obtained. However, most practical situations do not conform to these conditions, which in conjunction with the inherent uncertainty in selecting appropriate mathematical models, can cause instability in the estimation process. In addition, the relationship between the contact state and the observed measurements is nonlinear. Therefore, any linearization procedures applied can introduce additional estimation errors. Under these conditions, alternative algorithms for finding peaks in these multi-dimensional function to provide efficient and reliable estimates are desired.
Variable gradient-based estimation techniques, such as Kalman filters or maximum likelihood estimators, are available to provide tracking estimates by searching for the peak of the target state density function. However, these techniques employ a search procedure based on the local gradient of the density function, which can lead to convergence to local maxima. Another potential problem associated with these algorithms is that they can diverge when the problem becomes ill-conditioned, such as when the measurements are very noisy or the data is sparse and intermittent. These conditions are especially prevalent when tracking with active or passive data in a shallow water environment.
Because of their processing stability, grid-based techniques have recently been applied to the target state estimation problem. Unlike their gradient-based counterparts, these techniques estimate the unknown contact parameters by direct reconstruction of the state density function. In this process, a grid of predetermined size and resolution is typically used, and the value of the density function is computed at all grid points. In principle, this computationally expensive technique can provide the desired efficacy, however, its shortcoming is a lack of efficiency. In addition, the grid must be properly placed, and the resolution and size must be appropriately selected in order to properly represent the contact state density.
Recently, efforts have been made to generate better solutions for problem solving through the use of genetic algorithm methodologies for finding peaks in non-linear functions. U.S. Pat. No. 5,148,513 to Koza et al., for example, relates to a non-linear genetic process for problem solving using co-evolving populations of entities. The iterative process described therein operates on a plurality of populations of problem solving entities. First, an activated entity in one of the plurality of populations performs, producing a result. The result is assigned a value and the value is associated with the producing entity. The value assigned is computed relative ti the performance of the entity in a population different from the evolving population. Next, entities having relatively high associated values are selected from the evolving population. Th selected entities perform either crossover or fitness proportionate reproduction. In addition, other operations such as mutation, permutation, define building blocks and editing may be used. Next, the newly created entities are added to the evolving population. Finally, one of the environmental populations switches roles with the evolving population and the process repeats for the new evolving population and the new environmental populations.
U.S. Pat. Nos. 5,222,192 and 5,255,345, both to Shaefer, relate to optimization techniques using genetic algorithm methodologies. The optimization method described therein finds the best solution to a problem of the kind for which there is a space of possible solutions. In the method, tokens take on values that represent trial solutions in accordance with a representational scheme that defines the relationships between given token values and corresponding trial solutions. By an iterative process, the values of the tokens are changed to explore the solution space and to converge on the best solution. For at least some iterations, characteristics of the tokens and/or the trial solutions are analyzed and the representational scheme for later iterations is modified based on the analysis for earlier iterations without interrupting the succession of iterations. In another aspect, a set of operators is made available to enable a user to implement any of at least two different algorithms.
U.S. Pat. No. 5,343,554 to Koza et al. relates to an apparatus and method for solving problems using automatic function definitions, for solving problems using recursion, and for performing data encoding. The apparatus and method create a population and then evolve that population to generate a result. When solving problems using automatic function definition, the Koza et al. apparatus and method initially create a population of entities. Each of the entities has sub-entities of internally and externally invoked sub-entities. The externally invoked sub-entities are capable of having actions, invocations of sub-entities which are invoked internally, and material. Also, each sub-entity which is invoked internally is capable of including actions, invocations of internally invocable sub-entities, material provided to the externally invocable sub-entity, and material. The population is then evolved to generate a solution to the problem. When using the process to solve problems using recursion, the entities in the population are constructed in such a manner as to explicitly represent the termination predicate, the base case and the non-base case of the recursion. Each entity has access to a name denoting that entity so as to allow recursive references. The population is then evolved to generate a solution to the problem. When encoding a set of data values into a procedure capable of approximating those data values, the apparatus and process initially create a population of entities. The population is then evolved to generate a solution to the problem.
U.S. Pat. No. 5,394,509 to Winston relates to a data processing system and method for search for improved results from the process which utilizes genetic learning and optimization processes. The process is controlled according to a trial set of parameters. Trial sets are selected on the basis of an overall ranking based on results of the process as performed with a trial set. The ranking may be based on quality, or on a combination of rankings based on both quality and diversity. The data processing system and method described therein are applicable to manufacturing processes, database search processes and the design of products.
State estimation algorithms typically used in target motion analysis systems typically employ models of platform kinematics, the environment, and sensors. The contact or target is assumed to be of constant velocity, while the ship which is observing the target, the own ship, is free to maneuver. Further, straight line signal propagation is assumed.
The contact state parameters for position and velocity have components X.sub.j defined as: EQU X.sub.j .epsilon.[R.sub.XT (t.sub.o), R.sub.YT (t.sub.o), V.sub.XT, V.sub.YT ], (1a)
where R.sub.XT (t.sub.o) and R.sub.YT (t.sub.o) are the Cartesian position components at time t.sub.o, and V.sub.XT and V.sub.YT are the corresponding velocity components. Thus, the target state vector X.sub.T is defined as: EQU X.sub.T =[R.sub.XT (t.sub.o)R.sub.YT (t.sub.o)V.sub.XT V.sub.YT ].sup.T.(1b )
The observer state is similarly defined as: EQU X.sub.O =[R.sub.XO (t.sub.o), R.sub.YO (t.sub.o), V.sub.XO, V.sub.YO ].sup.T. (1c)
The contact state relative to the observer is defined as EQU X(t.sub.o)=X.sub.T -X.sub.O =[R.sub.X (t.sub.o), R.sub.Y (t.sub.o), V.sub.X, V.sub.Y ].sup.T, (1d)
where R.sub.X (t.sub.o) and R.sub.Y (t.sub.o) are the relative Cartesian position components at time t.sub.o, and V.sub.X and V.sub.Y are the relative velocity components. If t.sub.i is the i.sup.th sampling time, the state dynamic equations are governed by the equation: EQU X(t.sub.i+1)=.PHI.(t.sub.i+1, t.sub.i)X(t.sub.i)+u(t.sub.i),(2a)
where .PHI. (t.sub.i+1, t.sub.i) is the state transition matrix defined as ##EQU1## with I.sub.2.times.2 being a two dimensional square identity matrix and u(t.sub.i) is a vector relating to ownship acceleration at time t.sub.i. The measurement vector Z is defined by the equation EQU Z=H(X)+.eta., (3a)
where H(X) is a nonlinear function relating Z to the state X; that is, with .beta..sub.i defined as an angular measurement and R.sub.i defined as a range measurement, ##EQU2## and .eta. is the white Gaussian noise vector defined as: EQU .eta.=[.eta..sub..beta.0 .eta..sub..beta.1 . . . .eta..sub..beta.m .eta..sub.R0 .eta..sub.R1 . . . .eta..sub.Rm ].sup.T, (5a)
with mean and covariance EQU E[.eta.]=0, (5b) ##EQU3##
Determining the maximum likelihood estimate (MLE) is equivalent to finding the X that minimizes the cost function .parallel.Z-H(X).parallel.; i.e., ##EQU4## Performing the above operation yields EQU X=[.PHI..sup.T J.sup.T W.sup.-1 J.PHI.].sup.-1 .PHI..sup.T J.sup.T W.sup.-1 Z, (7)
where ##EQU5## is the Jacobean.
The term [.PHI..sup.T J.sup.T W.sup.-1 J.PHI.] in equation 7 is the Fisher Information Matrix (FIM) which must be nonsingular for X to be uniquely determined from the data. Because this is a gradient-based technique, the cost function and its derivative must be continuous. Inherent to the problem formulation are assumed system models. However, in many situations the models may not be known exactly. Traditional methods of solving the nonlinear tracking problem are sensitive to noise and geometric conditions, as well as modeling, linearization and initialization errors. These sources of error can cause problems by injecting errors in the computation of J and thus the FIM. As such these methods may be prone to ill-conditioning and instability.
For this reason, there still remains a need for more efficient systems and methods for estimating the motion of a target.